import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/1 20:10
 * @description 动态规划
 */
public class Solution {
    public static void main(String[] args) {

    }
    public boolean canCross(int[] stones) {
        int n = stones.length;
        // dp[i][k]表示青蛙能否到达 i处石头 且 上一次跳跃距离为 k
        boolean[][] dp = new boolean[n][n];
        dp[0][0] = true;
        for (int i = 1; i < n; i++) {
            if (stones[i] - stones[i - 1] > i) {
                // 每一次跳跃距离最多 +1，那么跳i次距离最远为 i
                return false;
            }
        }
        for (int i = 1; i < n; ++i) {
            for (int j = i - 1; j >= 0; --j) {
                int k = stones[i] - stones[j];
                if (k > j + 1) {
                    break;
                }
                dp[i][k] = dp[j][k - 1] || dp[j][k] || dp[j][k + 1];
                if (i == n - 1 && dp[i][k]) {
                    return true;
                }
            }
        }
        return false;
    }
}
